
package tsp;
import java.io.BufferedWriter;
import java.io.IOException;
import java.util.ArrayList;


public class BusquedaLocal 
{	
	
	
	public int cantNodos;	
	private Integer nodoV;	
	private Integer[][] pesoEjes;
	public int iteracionesSinMejorar;
	public Integer contadorItSM;
	private ArrayList<Integer> circuito1 = new ArrayList<Integer>();
	private ArrayList<Integer> circuito2 = new ArrayList<Integer>();
	
	private int pesoCircuito1 = pesoCircuito(circuito1);
	private int pesoCircuito2 = pesoCircuito(circuito2);
	
	private int longMinHastaAhora;
	
	public long cantOperaciones = 0L;	
	

	//funcion de marcos :D
	public Integer longitud(Integer a, Integer b)
	{
		if(a < b) 
			return pesoEjes[a][b-1-a];
		else
			return pesoEjes[b][a-1-b];
	}
	
	//asume que al menos tengo al menos 1 eje (o sea 2 nodos)
	//suma todos los pesos de los ejes, que va consultando en pesoEjes de a pares de nodos 
	public int pesoCircuito (ArrayList<Integer> circ)
	{	
		int peso = 0;	

		Integer nodoIni;		
		Integer nodoFin;
		
		int cantNodosCirc = circ.size();	
		int i;
		
		//recorre el circuito, y va sumando el peso del eje actual  
		for(i = 0; i < cantNodosCirc - 1; i++)
		{	
			
			cantOperaciones++;
			nodoIni = circ.get(i);
			nodoFin = circ.get(i + 1);		
			peso+=longitud(nodoIni, nodoFin);
					
		}
		if( i > 0 )
			peso+=longitud(circ.get(i), circ.get(0));
		
		return peso;
	}	
	
	//muestra el peso de los ejes de todo el grafo original
	public void mostrarPesoEjes()
	{		
		//System.out.println("Peso de los ejes del grafo");
		int cantFilas = pesoEjes.length;
		int cantColumnas = 0;
		
		for(int i = 0; i < cantFilas; i++)
		{
			cantColumnas = pesoEjes[i].length;
			
			for(int j = 0; j< cantColumnas; j++)
			{				
				if(j == (cantColumnas - 1))
					System.out.println(pesoEjes[i][j]);
				else
					System.out.print(pesoEjes[i][j] + " ");				
			}
		}
	}
		
	
	public int getPesoCircuito1() {
		return pesoCircuito1;
	}

	public void setPesoCircuito1(int pesoCircuito1) {
		this.pesoCircuito1 = pesoCircuito1;
	}

	public int getPesoCircuito2() {
		return pesoCircuito2;
	}

	public void setPesoCircuito2(int pesoCircuito2) {
		this.pesoCircuito2 = pesoCircuito2;
	}

	public long getCantOperaciones() {
		return cantOperaciones;
	}

	public void setCantOperaciones(int cantOperaciones) {
		this.cantOperaciones = cantOperaciones;
	}
		
	public int getCantNodos() {
		return cantNodos;
	}

	public void setCantNodos(int cantNodos) {
		this.cantNodos = cantNodos;
		this.iteracionesSinMejorar = cantNodos*5;
		this.contadorItSM = cantNodos;
	}

	public Integer getNodoV() {
		return nodoV;
	}

	public void setNodoV(Integer nodoV) {
		this.nodoV = nodoV-1;
	}

	public int getLongMinHastaAhora() {
		return longMinHastaAhora;
	}

	public void setLongMinHastaAhora(int longMinHastaAhora) {
		this.longMinHastaAhora = longMinHastaAhora;
	}
	
	public Integer[][] getPesoEjes() {
		return pesoEjes;
	}
	
	public void setPesoEjes(Integer[][] pesoEjes) {
		this.pesoEjes = pesoEjes;
	}
	
	public ArrayList<Integer> getCircuito1() {
		return circuito1;
	}

	public void setCircuito1(ArrayList<Integer> circuito1) {
		this.circuito1 = circuito1;
	}

	public ArrayList<Integer> getCircuito2() {
		return circuito2;
	}

	public void setCircuito2(ArrayList<Integer> circuito2) {
		this.circuito2 = circuito2;
	}	
	
	/******************* algoritmos para Tabu Search *****************************/
	// Con esta funcion, 
	public boolean bestMove(ArrayList<Eje[]> listaTabu, int tamTabu)
	{	
	/*	int nodoCorte = 0;
		int diferenciaMax = 0;
		
		//analizo cada casos por separado
		
		//caso1: cuando la solucion del algoritmo constructivo es 1 solo circuito 
		//la idea es partirlo en dos circs, luego calcular los vecinos y devolver el mejor
		if(circuito2.size() == 1 && circuito1.size() > 1)
		{	
			//busco el nodo de corte (nodoCorte)
			for(int i = 1; i < circuito1.size()-1; i++)
			{			
				Integer pesoAristaActual = longitud(circuito1.get(i), circuito1.get(i + 1));
				Integer pesoAristaIaNodoV = longitud(circuito1.get(i),getNodoV());
				Integer pesoAristaImas1ANodoV = longitud(circuito1.get(i + 1),getNodoV());				
				cantOperaciones = cantOperaciones + 3;
													
				if((pesoAristaActual > pesoAristaIaNodoV + pesoAristaImas1ANodoV) && 
				   (pesoAristaActual - pesoAristaIaNodoV - pesoAristaImas1ANodoV) > diferenciaMax)
				{		
					nodoCorte = i;					
					diferenciaMax = pesoAristaActual - pesoAristaIaNodoV - pesoAristaImas1ANodoV;					
					cantOperaciones = cantOperaciones + 2;
				}				
			}
			
			if (nodoCorte == 0)
			{
				//seteo los pesos de los circuitos vecinos encontrados 
				setPesoCircuito1(pesoCircuito(circuito1));
				setPesoCircuito2(pesoCircuito(circuito2));
				System.out.println(diferenciaMax);
				return true;
			}
			else
			{				
				//muevo todos los nodos desde el nodo de corte hasta el ultimo,  
				//del circuito 1 al (nuevo) circ2 
				for(int i = nodoCorte; i < circuito1.size(); i++)
				{
					circuito2.add(circuito1.get(nodoCorte));
					circuito1.remove(nodoCorte);					
					cantOperaciones = cantOperaciones + 2;
				}				
			}			
		}
		*/
		//caso2: que el algoritmos constructivo devuelva 2 circuitos
		boolean parada = darVecinosCruzandoTabu(nodoV, circuito1, circuito2, listaTabu, tamTabu);
		
		//seteo los pesos de los circuitos vecinos encontrados 
		setPesoCircuito1(pesoCircuito(circuito1));
		setPesoCircuito2(pesoCircuito(circuito2));
/***** Esto esta mal!! la longitud de aca abajo deberia ser igual a la longitud mejorada del darVecinosCruzadoTAbu*****/
		System.out.println("Longittuuuuuuuuuuuuuuuuuuuuuuuuud!!!: " + (pesoCircuito(circuito1) + pesoCircuito(circuito2)));
		
		return parada;	
		
	}
	
	//: ESTA FUNCION CALCULA LOS VECINOS TENIENDO EN CUENTA LOS NODOS DE LOS DOS CIRCUITOS,
	// sino que devuelve el mejor movimiento, y lo agrega a la listaTabu.
	private boolean darVecinosCruzandoTabu(Integer nodoV, ArrayList<Integer> circ1, ArrayList<Integer> circ2, ArrayList<Eje[]> listaTabu, int tamTabu)	
	{	
		int longCirc1 = circ1.size();
		
		ArrayList<Integer> circTemp1 = (ArrayList<Integer>) circ1.clone();
		ArrayList<Integer> circTemp2 = (ArrayList<Integer>) circ2.clone();	
		ArrayList<Integer> circRes1 = new ArrayList<Integer>(); // solcicion mejorada
		ArrayList<Integer> circRes2 = new ArrayList<Integer>(); // solcuoin mejorada
		
		ArrayList<Integer> circBest1 =  new ArrayList<Integer>(nodoV); // mejor sol empeorada
		ArrayList<Integer> circBest2 = new ArrayList<Integer>(nodoV);
		
		int pesoCircsOri = pesoCircuito(circ1) + pesoCircuito(circ2);				
		int pesoCircsAct = pesoCircuito(circTemp1) + pesoCircuito(circTemp2);
	
	//	Integer nodoCirc1;
	//	Integer nodoCirc2;	
		boolean todosTabu =true;
		Eje ejeBestMoveC1 = new Eje();
//		int iNodoBestMoveC1 = -1;
		Eje ejeBestMoveC2 = new Eje();
//		int iNodoBestMoveC2 = -1;
		boolean hayMov = false;
		boolean hayMejora = false;
		
		
		Eje eje1 = new Eje();
		Eje eje2 = new Eje();
		Eje[] parTabu = {eje1,eje2};
		parTabu[0] = eje1;
		parTabu[1] = eje2;
		int bestPesoCicsAct = (int) Integer.MAX_VALUE;
		//recorro todos los nodos del circ1, y voy buscando si existe algun
		//vecino que se forme intercambiando nodos del circ2 con los del circ1

		//longitudes de los circuitos
			int cantNodosCirc1 = circ1.size();
			int cantNodosCirc2 = circ2.size();
			
			//deberia ser igual a n, le resto 1 porque sino cuento 2 veces el nodoV
			int cantNodosTotal = cantNodosCirc1 + cantNodosCirc2 - 1;		
			if(cantNodosTotal != cantNodos)
				//no deberia entrar nunca aca!
				System.err.println("Error: la cantidad de nodos totales de los dos circuitos no es igual a n");
			
			
			//circuitos temporales	
			ArrayList<Integer> circ1Temp = new ArrayList<Integer>();
			ArrayList<Integer> circ2Temp = new ArrayList<Integer>();		
			//circuitos que seran la mejor solucion hasta el momento, posiblemente los que se devuelvan como solucion 
			ArrayList<Integer> circ1Res = new ArrayList<Integer>(circ1);
			ArrayList<Integer> circ2Res = new ArrayList<Integer>(circ2);
			
			
			//peso total, la suma del peso de cada circuito original,
			//y se lo asigno a una variable que luego sera el mejor peso hasta el momento
			int mejorPesoHastaAhora = pesoCircuito(circ1) + pesoCircuito(circ2);		
			//suma de los pesos de los dos circs Temporales
			int pesoCircsTemp = 0;
					
			Integer nodo1;
			Integer nodo2;
			Integer nodo3;
			Integer nodo4;
			
			//recorro el circuito1 original		
			for(int i = 0; i < circ1.size(); i++)
			{
				
				
				//levanto el nodo 1 y el nodo2 del circuito 1 
				nodo1 = new Integer(circ1.get(i));
				
				//si estoy en el ultimo nodo del circuito, el siguiente es el nodoV
				if(i == circ1.size() - 1)
					nodo2 = nodoV;
				else
					nodo2 = new Integer(circ1.get(i + 1));
				
				
				//recorro el circuito2 original
				for(int j = 0; j < circ2.size(); j++)
				{
					cantOperaciones++;
					
					//levanto el nodo 3 y el nodo 4 del circuito 2 
					nodo3 = new Integer(circ2.get(j));
					
					//si estoy en el ultimo nodo del circuito, el siguiente es el nodoV
					if(j == circ2.size() - 1)
						nodo4 = nodoV;
					else
						nodo4 = new Integer(circ2.get(j + 1));
					
					eje1.head = new Integer(nodo1);
					eje1.tail = new Integer(nodo2);
					eje2.head = new Integer(nodo3);
					eje2.tail = new Integer(nodo4);
					
					//Chequeo que no sean tabu	
					if(!sonTabu(eje1,eje2, listaTabu)){
					todosTabu = false;
					//analizo cada caso por separado
					
					/*********** CASO 2 *********************/
					// ambas aristas tienen incidente al nodoV
					
					circ1Temp.clear();
					circ2Temp.clear();
					
					if(nodo1.equals(nodoV))
					{
						if(nodo3.equals(nodoV))
							// ambas al inicio, 
							// nodo2--nodo4
						{

							//circ1Temp
			            	
			            	circ1Temp.add(new Integer(nodoV));
							//recorro el circ2 desde el final hasta el nodo4,
							//y voy copiando los nodos en el circ1Temp al reves
							for(int k = circ2.size()-1; k >= j+1 ; k--)
							{
								circ1Temp.add(circ2.get(k));
								cantOperaciones++;
							}	
							
							//recorro el circ1 desde el nodo2 hasta el final,
							//y voy copiando los nodos en el circ1Temp
							for(int k = i+1; k < circ1.size(); k++)
							{
								circ1Temp.add(circ1.get(k));
								cantOperaciones++;
							}
							
							if(circ2Temp.size() == 0 || !circ2Temp.get(0).equals(nodoV))
								circ2Temp.add(0,new Integer(nodoV));
							pesoCircsTemp = pesoCircuito(circ1Temp) + pesoCircuito(circ2Temp);
							if(pesoCircsTemp < (pesoCircuito(circ1Res)+pesoCircuito(circ2Res))){
								circ1Res = (ArrayList<Integer>)circ1Temp.clone();
								circ2Res = (ArrayList<Integer>)circ2Temp.clone();
								hayMejora = true;
							}
							
						
						}	
						else
							if(nodo4.equals(nodoV))
							// nodo2--nodo3	
							{
							
								//recorro el circ2 desde el inicio hasta el nodo3,
								//y voy copiando los nodos en el circ1Temp
								for(int k = 0; k <= j; k++)
								{
									circ1Temp.add(circ2.get(k));
									cantOperaciones++;
								}
				            	
								//recorro el circ1 desde el nodo2 hasta el final,
								//y voy copiando los nodos en el circ1Temp
								for(int k = i+1; k < circ1.size(); k++)
								{
									circ1Temp.add(circ1.get(k));
									cantOperaciones++;
								}
								
								// chequeo que no sean tabu
								if(circ2Temp.size() == 0 || !circ2Temp.get(0).equals(nodoV))
									circ2Temp.add(0,new Integer(nodoV));
								pesoCircsTemp = pesoCircuito(circ1Temp) + pesoCircuito(circ2Temp);
								if(pesoCircsTemp < (pesoCircuito(circ1Res)+pesoCircuito(circ2Res))){
									circ1Res = (ArrayList<Integer>)circ1Temp.clone();
									circ2Res = (ArrayList<Integer>)circ2Temp.clone();
									hayMejora = true;
								}
														
							}
					

					}
					else if(nodo2.equals(nodoV))
						{
							if(nodo3.equals(nodoV))
							// nodo1--nodo4	
							{
								
								//recorro el circ1 desde el inicio hasta el nodo1,
								//y voy copiando los nodos en el circ1Temp
								for(int k = 0; k <= i; k++)
								{
									circ1Temp.add(circ1.get(k));
									cantOperaciones++;
								}
								//recorro el circ2 desde el nodo4 hasta el final,
								//y voy copiando los nodos en el circ1Temp
								for(int k = j+1; k < circ2.size(); k++)
								{
									circ1Temp.add(circ2.get(k));
									cantOperaciones++;
								}
								
								if(circ2Temp.size() == 0 || !circ2Temp.get(0).equals(nodoV))
									circ2Temp.add(0,new Integer(nodoV));
								pesoCircsTemp = pesoCircuito(circ1Temp) + pesoCircuito(circ2Temp);
								if(pesoCircsTemp < (pesoCircuito(circ1Res)+pesoCircuito(circ2Res))){
									circ1Res = (ArrayList<Integer>)circ1Temp.clone();
									circ2Res = (ArrayList<Integer>)circ2Temp.clone();
									hayMejora = true;
								}
								
							}	
							else
								if(nodo4.equals(nodoV))
								// ambas al final, nodo1--nodo3
								{
					            	//circ1Temp
									//recorro el circ1 desde el 0 hasta el nodo1,
									//y voy copiando los nodos en el circ1Temp
									for(int k = 0; k <= i; k++)
									{
										circ1Temp.add(circ1.get(k));
										cantOperaciones++;
									}	
									
									//recorro el circ2 desde el nodo3 hasta el final,
									//y voy copiando los nodos en el circ1Temp
									for(int k = 1; k< circ2.size(); k++)
									{
										circ1Temp.add(circ2.get(k));
										cantOperaciones++;
									}
									
									if(circ2Temp.size() == 0 || !circ2Temp.get(0).equals(nodoV))
										circ2Temp.add(0,new Integer(nodoV));
									pesoCircsTemp = pesoCircuito(circ1Temp) + pesoCircuito(circ2Temp);
									if(pesoCircsTemp < (pesoCircuito(circ1Res)+pesoCircuito(circ2Res))){
										circ1Res = (ArrayList<Integer>)circ1Temp.clone();
										circ2Res = (ArrayList<Integer>)circ2Temp.clone();
										hayMejora = true;
									}
									
									// chequeo que no sean tabu
									if((pesoCircsTemp > (pesoCircuito(circ1)+pesoCircuito(circ1)))&& (pesoCircsTemp < (pesoCircuito(circBest1)+pesoCircuito(circBest2)))){
										circBest1 = (ArrayList<Integer>)circ1Temp.clone();
										circBest2 = (ArrayList<Integer>)circ2Temp.clone();
										
										parTabu[0] = eje1;
										parTabu[1] = eje2;
									}
									
								
								}						
									
		
					
				}
					
				/*********** CASO 1 *********************/
				//una aristas no es incidente al nodoV
					else{									
					
						circ1Temp.clear();
						circ2Temp.clear();
						//CASO 1_B
						//intercambio "derecho": nodo1-nodo4 y nodo2-nodo3
											
						eje1.head = new Integer(nodo1);
						eje1.tail = new Integer(nodo4);
						eje2.head = new Integer(nodo2);
						eje2.tail = new Integer(nodo3);
						
						
						//circ1Temp:
						//recorro el circ1 desde el inicio hasta el nodo1, 
						//y voy copiando los nodos en el circ1Temp
						for(int k = 0; k <= i; k++)
						{
							circ1Temp.add(new Integer (circ1.get(k)));
							cantOperaciones++;
						}						

						//recorreo el circ2 desde el nodo4 hasta el final, 
						//y los voy copiando en el circ1Temp	
						for(int l = j+1; l < circ2.size(); l++)
						{			
							circ1Temp.add(circ2.get(l));
							cantOperaciones++;
						}
						
						//circ2Temp:
						//recorro el circ2 desde el inicio hasta el nodo3, 
						//y voy copiando los nodos en el circ2Temp
						for(int k = 0; k <= j; k++)
						{
							circ2Temp.add(circ2.get(k));
							cantOperaciones++;
						}					
						//recorro el circ1 desde el nodo2 (i+1) hasta el final,
						//y voy copiando los nodos en el circ2Temp
						for(int k = i+1; k < circ1.size(); k++)
						{
							circ2Temp.add(circ1.get(k));
							cantOperaciones++;
						}					
						
						if(circ2Temp.size() == 0 || !circ2Temp.get(0).equals(nodoV))	
							circ2Temp.add(0,new Integer(nodoV));
						
						pesoCircsTemp = pesoCircuito(circ1Temp) + pesoCircuito(circ2Temp);
						if(pesoCircsTemp < (pesoCircuito(circ1Res)+pesoCircuito(circ2Res))){
							circ1Res = (ArrayList<Integer>)circ1Temp.clone();
							circ2Res = (ArrayList<Integer>)circ2Temp.clone();
							hayMejora = true;
						}
						
						// chequeo que no sean tabu
						if((pesoCircsTemp > (pesoCircuito(circ1)+pesoCircuito(circ1)))&& (pesoCircsTemp < (pesoCircuito(circBest1)+pesoCircuito(circBest2)))){
							circBest1 = (ArrayList<Integer>)circ1Temp.clone();
							circBest2 = (ArrayList<Integer>)circ2Temp.clone();
							
							parTabu[0] = eje1;
							parTabu[1] = eje2;
						}
					
						//CASO 1_A
						//intercambio "cruzado": nodo1-nodo3 y nodo2-nodo4
						//puede variar la long de los circuitos 1 y 2 solucion
						
						circ1Temp.clear();
						circ2Temp.clear();
						
						eje1.head = new Integer(nodo1);
						eje1.tail = new Integer(nodo3);
						eje2.head = new Integer(nodo2);
						eje2.tail = new Integer(nodo4);
						
						//circ1Temp:
						//recorro el circ1 desde el inicio hasta el nodo1, 
						//y voy copiando los nodos en el circ1Temp
						for(int k = 0; k <= i; k++)
						{
							circ1Temp.add(new Integer (circ1.get(k)));
							cantOperaciones++;
						}						

						//recorro el circ2 desde el nodo3 hasta el principio, 
						//y voy copiando los nodos en el circ1Temp al reves
						for(int k = j; k > 0; k--)
						{
							circ1Temp.add(new Integer (circ2.get(k)));
							cantOperaciones++;
						}	
						
						//circ2Temp:
						
						//recorro el circ2 desde el final hasta el nodo4(j+1),
						//y voy copiando los nodos en el circ2Temp
						for(int k = circ2.size()-1; k >= j+1; k--)
						{
							circ2Temp.add(circ2.get(k));
							cantOperaciones++;
						}	
						
						//recorro el circ1 desde el nodo2 (i+1) hasta el final,
						//y voy copiando los nodos en el circ2Temp
						for(int k = i+1; k < circ1.size(); k++)
						{
							circ2Temp.add(circ1.get(k));
							cantOperaciones++;
						}
						
					
		
				/**********************************************************************/
						if(circ2Temp.size() == 0 || !circ2Temp.get(0).equals(nodoV))	
							circ2Temp.add(0,new Integer(nodoV));
						
						pesoCircsTemp = pesoCircuito(circ1Temp) + pesoCircuito(circ2Temp);
						if(pesoCircsTemp < (pesoCircuito(circ1Res)+pesoCircuito(circ2Res))){
							circ1Res = (ArrayList<Integer>)circ1Temp.clone();
							circ2Res = (ArrayList<Integer>)circ2Temp.clone();
							hayMejora = true;
						}

						// chequeo que no sean tabu
						if((pesoCircsTemp > (pesoCircuito(circ1)+pesoCircuito(circ1)))&& (pesoCircsTemp < (pesoCircuito(circBest1)+pesoCircuito(circBest2)))){
							circBest1 = (ArrayList<Integer>)circ1Temp.clone();
							circBest2 = (ArrayList<Integer>)circ2Temp.clone();
							
							parTabu[0] = eje1;
							parTabu[1] = eje2;
						}	
				}			
		}
					}
	 }
				
	
		
		if (todosTabu) return true;
		if(!hayMejora){ //&& circ2.size()>2){
			circ1 = (ArrayList<Integer>) circBest1.clone();
			circ2 = (ArrayList<Integer>) circBest2.clone();
			listaTabu.add(parTabu);
			contadorItSM = contadorItSM -1;
				return false;
		}
		
		// hubo mejora
		listaTabu.add(parTabu);
		contadorItSM = iteracionesSinMejorar;
		circ1 = (ArrayList<Integer>) circ1Res.clone();
		circ2 = (ArrayList<Integer>) circ2Res.clone();
		
		circuito1 = (ArrayList<Integer>)circ1.clone();
		circuito2 = (ArrayList<Integer>)circ2.clone();
		
		setPesoCircuito1(pesoCircuito(circuito1));
		setPesoCircuito2(pesoCircuito(circuito2));
		
		return false;
	}
	
	boolean sonTabu(Eje eje1, Eje eje2, ArrayList<Eje[]> listaTabu)
	{
		for(Eje[] parEjes : listaTabu)
		{
			cantOperaciones++;
			if ((parEjes[0].igual(eje1) && parEjes[1].igual(eje2)) ||
				(parEjes[1].igual(eje1) && parEjes[0].igual(eje2)))
				return true;
		}
		return false;
	}
	public void busquedaLocalTSP() 
	{	
		int nodoCorte = 0;
		int diferenciaMax = 0;
		
		//analizo cada casos por separado
		/*** PRUEBAS **/
/*		circuito1.clear();
		circuito2.clear();
		circuito1.add(new Integer(nodoV));
		for(int i = 0; i<cantNodos;i++){
			if(!nodoV.equals(i))
				circuito1.add(new Integer(i));
			else{
				i++;
			circuito1.add(new Integer(i));
			}
		}
		
		
		circuito2.add(new Integer(nodoV));
		for(int i = circuito1.size()-1; i>cantNodos/2;i--){
				circuito2.add(new Integer(circuito1.get(circuito1.size()-1)));
				circuito1.remove(circuito1.size()-1);
		}
		ArrayList<Integer> circuito3 = new ArrayList<Integer>();
		circuito3= (ArrayList<Integer>) circuito2.clone();
		circuito2.clear();
		circuito2.add(nodoV);
		circuito3.remove(0);
		for(int i=circuito3.size()-1;i>=0;i--){
			circuito2.add(circuito3.get(i));
		}
		
		int tamTotal = (pesoCircuito(circuito1)+pesoCircuito(circuito2));
		
		dif.write(tamTotal+" ");
		*/
		//caso1: cuando la solucion del algoritmo constructivo es 1 solo circuito 
		//la idea es partirlo en dos circs, luego calcular los vecinos y devolver el mejor
		if(circuito2.size() == 1 && circuito1.size() > 1)
		{	
			//busco el nodo de corte (nodoCorte)
			for(int i = 1; i < circuito1.size()-1; i++)
			{			
				Integer pesoAristaActual = longitud(circuito1.get(i), circuito1.get(i + 1));
				Integer pesoAristaIaNodoV = longitud(circuito1.get(i),getNodoV());
				Integer pesoAristaImas1ANodoV = longitud(circuito1.get(i + 1),getNodoV());				
				cantOperaciones++;
													
				if((pesoAristaActual > pesoAristaIaNodoV + pesoAristaImas1ANodoV) && 
				   (pesoAristaActual - pesoAristaIaNodoV - pesoAristaImas1ANodoV) > diferenciaMax)
				{				
					nodoCorte = i;					
					diferenciaMax = pesoAristaActual - pesoAristaIaNodoV - pesoAristaImas1ANodoV;					

				}				
			}
			
			if (nodoCorte == 0)
			{
				//seteo los pesos de los circuitos vecinos encontrados 
				setPesoCircuito1(pesoCircuito(circuito1));
				setPesoCircuito2(pesoCircuito(circuito2));
				
				return;
			}
			else
			{				
				//muevo todos los nodos desde el nodo de corte hasta el ultimo,  
				//del circuito 1 al (nuevo) circ2 
				for(int i = nodoCorte; i < circuito1.size(); i++)
				{
					circuito2.add(circuito1.get(nodoCorte));
					circuito1.remove(nodoCorte);					
					cantOperaciones++;
				}				
			}			
		}
		
		//ANTES hacia		
		//darVecinosCruzando(nodoV, circuito1, circuito2);
		
		//AHORA NUEVA2 solucion **** SOLE
		/*
		Circuito circ1 = new Circuito();
		circ1.tam = circuito1.size();
		Nodo inicial = new Nodo();
		inicial.id = 0;
		circ1.inicio = inicial;
		Nodo nAnt = inicial;
		for(int k = 1; k < circuito1.size(); k++){
			if(k == 1){
				Nodo nuevo = new Nodo();
				nuevo.id = k;
				nuevo.ant = inicial;
				inicial.prox = nuevo;
				nAnt = nuevo;
			}
		
			Nodo nuevo = new Nodo();
			nuevo.id = k;
			nAnt.prox = nuevo; 
			nuevo.ant = nAnt;
			nAnt = nuevo;
		}
		
		Circuito circ2 = new Circuito();
		circ2.tam = circuito2.size();
		
		inicial = new Nodo();
		inicial.id = 0;
		circ2.inicio = inicial;
		
		for(int k = 1; k < circuito2.size(); k++){
			if(k == 1){
				Nodo nuevo = new Nodo();
				nuevo.id = k;
				nuevo.ant = inicial;
				inicial.prox = nuevo;
				nAnt = nuevo;
			}
		
			Nodo nuevo = new Nodo();
			nuevo.id = k;
			nAnt.prox = nuevo; 
			nuevo.ant = nAnt;
			nAnt = nuevo;
		}
		
		calcularMejorVecino2(circ1, circ2);
		*/		
		calcularMejorVecino(nodoV, circuito1, circuito2);
		
		setPesoCircuito1(pesoCircuito(circuito1));
		setPesoCircuito2(pesoCircuito(circuito2));
		
	}
	/*
	private void calcularMejorVecino2(Circuito circ1, Circuito circ2)
	{
	
		//circuitos temporales	
		Circuito circ1Temp = new Circuito();
		Circuito circ2Temp = new Circuito();	
		//circuitos que seran la mejor solucion hasta el momento, posiblemente los que se devuelvan como solucion 
		Circuito circ1Res = new Circuito();
		Circuito circ2Res = new Circuito();
		
		
		//peso total, la suma del peso de cada circuito original,
		//y se lo asigno a una variable que luego sera el mejor peso hasta el momento
		int mejorPesoHastaAhora = pesoCircuito(circ1) + pesoCircuito(circ2);		
		//suma de los pesos de los dos circs Temporales
		int pesoCircsTemp = 0;
				
		Nodo nodo1;
		Nodo nodo2;
		Nodo nodo3;
		Nodo nodo4;
		Nodo nodoTemp;
		
		boolean hayMejora = true;
	while(hayMejora){	
		hayMejora = false;
		//recorro el circuito1 original		
		for(int i = 0; i < circ1.tam; i++)
		{
		
			//recorro el circuito2 original
			for(int j = 0; j < circ2.tam; j++)
			{
				//analizo cada caso por separado
				circ1Temp.clone(circ1);
				circ2Temp.clone(circ2);
				
				nodo1 = circ1Temp.getNodo(i);
				nodo3 = circ2Temp.getNodo(j);
				
				//si estoy en el ultimo nodo del circuito, el siguiente es el nodoV
				if(i == circ1.tam - 1)
					nodo2 = circ1Temp.inicio;
				else
					nodo2 = circ1Temp.getNodo(i+1);
				
				//si estoy en el ultimo nodo del circuito, el siguiente es el nodoV
				if(j == circ2.tam - 1)
					nodo4 = circ2Temp.inicio;
				else
					nodo4 = circ2Temp.getNodo(j+1);
						
				/*********** CASO 1 ********************
				//ambas aristas no contienen al nodoV en ninguno de sus dos extremos
				if(!nodo1.equals(nodoV) && !nodo2.equals(nodoV) && !nodo3.equals(nodoV) && !nodo4.equals(nodoV))
				{									
				
					
					//CASO 1_B
					//intercambio "cruzado": nodo1-nodo4 y nodo2-nodo3

					//circ1Temp..
					nodo1.prox = nodo4;
					nodo4.ant = nodo1;
					
					// circ2Temp
					nodo2.ant = nodo3;
					nodo3.prox = nodo2;

					
					pesoCircsTemp = pesoCircuito(circ1Temp) + pesoCircuito(circ2Temp);
					if(pesoCircsTemp < (pesoCircuito(circ1Res)+pesoCircuito(circ2Res))){
						circ1Res = (ArrayList<Integer>)circ1Temp.clone();
						circ2Res = (ArrayList<Integer>)circ2Temp.clone();
						hayMejora = true;
					}
					

				
					//CASO 1_A
					//intercambio "derecho": nodo1-nodo3 y nodo2-nodo4
					
					
					//circ1Temp:

					nodo1.prox = nodo3;
					nodo3.ant = nodo1;
					
					//circ2Temp:

					circ2Temp.inicio.prox = nodo2;
					nodo2.ant = circ2Temp.inicio;
					circ1.ult().prox = nodo4;
					
					//recorro el circ2 desde el inicio hasta el nodo2, 
					//y voy copiando los nodos en el circ1Temp
					for(int k = 0; k < j + 1; k++)
					{
						System.out.println("circ1Temp.size = " + circ1Temp.size() +	"k = " + k);						
						circ1Temp.add(new Integer (circ2.get(k)));
						cantOperaciones++;
					}	
					
					//circ2Temp:
					
					//recorro el circ1 desde el nodo2 (i+1) hasta el final,
					//y voy copiando los nodos en el circ2Temp
					// agrego el nodo inicial 
					circ2Temp.add(circ1.get(0));
					for(int k = i+1; k < cantNodosCirc1; k++)
					{
						circ2Temp.add(circ1.get(k));
						cantOperaciones++;
					}
					
					//recorro el circ2 desde el nodo3 (j+1) hasta el final,
					//y voy copiando los nodos en el circ2Temp
					for(int k = j+1; k < cantNodosCirc2; k++)
					{
						circ2Temp.add(circ2.get(k));
						cantOperaciones++;
					}					
	
			/*********************************************************************
					
					pesoCircsTemp = pesoCircuito(circ1Temp) + pesoCircuito(circ2Temp);
					if(pesoCircsTemp < (pesoCircuito(circ1Res)+pesoCircuito(circ2Res))){
						circ1Res = (ArrayList<Integer>)circ1Temp.clone();
						circ2Res = (ArrayList<Integer>)circ2Temp.clone();
						hayMejora = true;
					}

	
				}			
				
			*********** CASO 3 *************************
				
			}
	}
*/
	//NUEVO!!! 
	//CALCULAR MEJOR VECINO: calculo la mejor solucion vecina intercambiando aristas entre los circuitos 
	private void calcularMejorVecino(Integer nodoV, ArrayList<Integer> circ1, ArrayList<Integer> circ2)
	{
		//longitudes de los circuitos
		int cantNodosCirc1 = circ1.size();
		int cantNodosCirc2 = circ2.size();
		
		//deberia ser igual a n, le resto 1 porque sino cuento 2 veces el nodoV
		int cantNodosTotal = cantNodosCirc1 + cantNodosCirc2 - 1;		
		if(cantNodosTotal != cantNodos)
			//no deberia entrar nunca aca!
			System.err.println("Error: la cantidad de nodos totales de los dos circuitos no es igual a n");
		
		
		//circuitos temporales	
		ArrayList<Integer> circ1Temp = new ArrayList<Integer>();
		ArrayList<Integer> circ2Temp = new ArrayList<Integer>();		
		//circuitos que seran la mejor solucion hasta el momento, posiblemente los que se devuelvan como solucion 
		ArrayList<Integer> circ1Res = new ArrayList<Integer>(circ1);
		ArrayList<Integer> circ2Res = new ArrayList<Integer>(circ2);
		
		
		//peso total, la suma del peso de cada circuito original,
		//y se lo asigno a una variable que luego sera el mejor peso hasta el momento
		int mejorPesoHastaAhora = pesoCircuito(circ1) + pesoCircuito(circ2);		
		//suma de los pesos de los dos circs Temporales
		int pesoCircsTemp = 0;
				
		Integer nodo1;
		Integer nodo2;
		Integer nodo3;
		Integer nodo4;
		Integer nodoTemp;
		
		boolean hayMejora = true;
	while(hayMejora && (circ1Res.size()!=cantNodos)){	
		hayMejora = false;
		//recorro el circuito1 original		
		for(int i = 0; i < circ1.size(); i++)
		{
			
			
			//levanto el nodo 1 y el nodo2 del circuito 1 
			nodo1 = new Integer(circ1.get(i));
			
			//si estoy en el ultimo nodo del circuito, el siguiente es el nodoV
			if(i == circ1.size() - 1)
				nodo2 = nodoV;
			else
				nodo2 = new Integer(circ1.get(i + 1));
			
			
			//recorro el circuito2 original
			for(int j = 0; j < circ2.size(); j++)
			{
				cantOperaciones++;
				
				//levanto el nodo 3 y el nodo 4 del circuito 2 
				nodo3 = new Integer(circ2.get(j));
				
				//si estoy en el ultimo nodo del circuito, el siguiente es el nodoV
				if(j == circ2.size() - 1)
					nodo4 = nodoV;
				else
					nodo4 = new Integer(circ2.get(j + 1));
								
				
				
				
				//analizo cada caso por separado
				
				/*********** CASO 2 *********************/
				// ambas aristas tienen incidente al nodoV
				
				circ1Temp.clear();
				circ2Temp.clear();
				
				if(nodo1.equals(nodoV))
				{
					if(nodo3.equals(nodoV))
						// ambas al inicio, 
						// nodo2--nodo4
					{
						//circ1Temp
		            	
		            	circ1Temp.add(new Integer(nodoV));
						//recorro el circ2 desde el final hasta el nodo4,
						//y voy copiando los nodos en el circ1Temp al reves
						for(int k = circ2.size()-1; k >= j+1 ; k--)
						{
							circ1Temp.add(circ2.get(k));
							cantOperaciones++;
						}	
						
						//recorro el circ1 desde el nodo2 hasta el final,
						//y voy copiando los nodos en el circ1Temp
						for(int k = i+1; k < circ1.size(); k++)
						{
							circ1Temp.add(circ1.get(k));
							cantOperaciones++;
						}
						
						if(circ2Temp.size() == 0 || !circ2Temp.get(0).equals(nodoV))
							circ2Temp.add(0,new Integer(nodoV));
						pesoCircsTemp = pesoCircuito(circ1Temp) + pesoCircuito(circ2Temp);
						if(pesoCircsTemp < (pesoCircuito(circ1Res)+pesoCircuito(circ2Res))){
							circ1Res = (ArrayList<Integer>)circ1Temp.clone();
							circ2Res = (ArrayList<Integer>)circ2Temp.clone();
							hayMejora = true;
						}
						
					}	
					else
						if(nodo4.equals(nodoV))
						// nodo2--nodo3	
						{
						
							//recorro el circ2 desde el inicio hasta el nodo3,
							//y voy copiando los nodos en el circ1Temp
							for(int k = 0; k <= j; k++)
							{
								circ1Temp.add(circ2.get(k));
								cantOperaciones++;
							}
			            	
							//recorro el circ1 desde el nodo2 hasta el final,
							//y voy copiando los nodos en el circ1Temp
							for(int k = i+1; k < circ1.size(); k++)
							{
								circ1Temp.add(circ1.get(k));
								cantOperaciones++;
							}
							
							if(circ2Temp.size() == 0 || !circ2Temp.get(0).equals(nodoV))
								circ2Temp.add(0,new Integer(nodoV));
							pesoCircsTemp = pesoCircuito(circ1Temp) + pesoCircuito(circ2Temp);
							if(pesoCircsTemp < (pesoCircuito(circ1Res)+pesoCircuito(circ2Res))){
								circ1Res = (ArrayList<Integer>)circ1Temp.clone();
								circ2Res = (ArrayList<Integer>)circ2Temp.clone();
								hayMejora = true;
							}
			            	
						
						}
				

				}
				else if(nodo2.equals(nodoV))
					{
						if(nodo3.equals(nodoV))
						// nodo1--nodo4	
						{
							
							//recorro el circ1 desde el inicio hasta el nodo1,
							//y voy copiando los nodos en el circ1Temp
							for(int k = 0; k <= i; k++)
							{
								circ1Temp.add(circ1.get(k));
								cantOperaciones++;
							}
							//recorro el circ2 desde el nodo4 hasta el final,
							//y voy copiando los nodos en el circ1Temp
							for(int k = j+1; k < circ2.size(); k++)
							{
								circ1Temp.add(circ2.get(k));
								cantOperaciones++;
							}
							
							if(circ2Temp.size() == 0 || !circ2Temp.get(0).equals(nodoV))
								circ2Temp.add(0,new Integer(nodoV));
							pesoCircsTemp = pesoCircuito(circ1Temp) + pesoCircuito(circ2Temp);
							if(pesoCircsTemp < (pesoCircuito(circ1Res)+pesoCircuito(circ2Res))){
								circ1Res = (ArrayList<Integer>)circ1Temp.clone();
								circ2Res = (ArrayList<Integer>)circ2Temp.clone();
								hayMejora = true;
							}
						}	
						else
							if(nodo4.equals(nodoV))
							// ambas al final, nodo1--nodo3
							{
				            	//circ1Temp
								//recorro el circ1 desde el 0 hasta el nodo1,
								//y voy copiando los nodos en el circ1Temp
								for(int k = 0; k <= i; k++)
								{
									circ1Temp.add(circ1.get(k));
									cantOperaciones++;
								}	
								
								//recorro el circ2 desde el nodo3 hasta el final,
								//y voy copiando los nodos en el circ1Temp
								for(int k = 1; k< circ2.size(); k++)
								{
									circ1Temp.add(circ2.get(k));
									cantOperaciones++;
								}
								
								if(circ2Temp.size() == 0 || !circ2Temp.get(0).equals(nodoV))
									circ2Temp.add(0,new Integer(nodoV));
								pesoCircsTemp = pesoCircuito(circ1Temp) + pesoCircuito(circ2Temp);
								if(pesoCircsTemp < (pesoCircuito(circ1Res)+pesoCircuito(circ2Res))){
									circ1Res = (ArrayList<Integer>)circ1Temp.clone();
									circ2Res = (ArrayList<Integer>)circ2Temp.clone();
									hayMejora = true;
								}
								
							
							}						
								
	
				
			}
				
			/*********** CASO 1 *********************/
			//una aristas no es incidente al nodoV
				else{									
				
					circ1Temp.clear();
					circ2Temp.clear();
					//CASO 1_B
					//intercambio "derecho": nodo1-nodo4 y nodo2-nodo3
										
					//circ1Temp:
					//recorro el circ1 desde el inicio hasta el nodo1, 
					//y voy copiando los nodos en el circ1Temp
					for(int k = 0; k <= i; k++)
					{
						circ1Temp.add(new Integer (circ1.get(k)));
						cantOperaciones++;
					}						

					//recorreo el circ2 desde el nodo4 hasta el final, 
					//y los voy copiando en el circ1Temp	
					for(int l = j+1; l < circ2.size(); l++)
					{			
						circ1Temp.add(circ2.get(l));
						cantOperaciones++;
					}
					
					//circ2Temp:
					//recorro el circ2 desde el inicio hasta el nodo3, 
					//y voy copiando los nodos en el circ2Temp
					for(int k = 0; k <= j; k++)
					{
						circ2Temp.add(circ2.get(k));
						cantOperaciones++;
					}					
					//recorro el circ1 desde el nodo2 (i+1) hasta el final,
					//y voy copiando los nodos en el circ2Temp
					for(int k = i+1; k < circ1.size(); k++)
					{
						circ2Temp.add(circ1.get(k));
						cantOperaciones++;
					}					
					
					if(circ2Temp.size() == 0 || !circ2Temp.get(0).equals(nodoV))	
						circ2Temp.add(0,new Integer(nodoV));
					
					pesoCircsTemp = pesoCircuito(circ1Temp) + pesoCircuito(circ2Temp);
					if(pesoCircsTemp < (pesoCircuito(circ1Res)+pesoCircuito(circ2Res))){
						circ1Res = (ArrayList<Integer>)circ1Temp.clone();
						circ2Res = (ArrayList<Integer>)circ2Temp.clone();
						hayMejora = true;
					}
					

				
					//CASO 1_A
					//intercambio "cruzado": nodo1-nodo3 y nodo2-nodo4
					//puede variar la long de los circuitos 1 y 2 solucion
					
					circ1Temp.clear();
					circ2Temp.clear();
					
					//circ1Temp:
					//recorro el circ1 desde el inicio hasta el nodo1, 
					//y voy copiando los nodos en el circ1Temp
					for(int k = 0; k <= i; k++)
					{
						circ1Temp.add(new Integer (circ1.get(k)));
						cantOperaciones++;
					}						

					//recorro el circ2 desde el nodo3 hasta el principio, 
					//y voy copiando los nodos en el circ1Temp al reves
					for(int k = j; k > 0; k--)
					{
						circ1Temp.add(new Integer (circ2.get(k)));
						cantOperaciones++;
					}	
					
					//circ2Temp:
					
					//recorro el circ2 desde el final hasta el nodo4(j+1),
					//y voy copiando los nodos en el circ2Temp
					for(int k = circ2.size()-1; k >= j+1; k--)
					{
						circ2Temp.add(circ2.get(k));
						cantOperaciones++;
					}	
					
					//recorro el circ1 desde el nodo2 (i+1) hasta el final,
					//y voy copiando los nodos en el circ2Temp
					for(int k = i+1; k < circ1.size(); k++)
					{
						circ2Temp.add(circ1.get(k));
						cantOperaciones++;
					}
					
				
	
			/**********************************************************************/
					if(circ2Temp.size() == 0 || !circ2Temp.get(0).equals(nodoV))	
						circ2Temp.add(0,new Integer(nodoV));
					
					pesoCircsTemp = pesoCircuito(circ1Temp) + pesoCircuito(circ2Temp);
					if(pesoCircsTemp < (pesoCircuito(circ1Res)+pesoCircuito(circ2Res))){
						circ1Res = (ArrayList<Integer>)circ1Temp.clone();
						circ2Res = (ArrayList<Integer>)circ2Temp.clone();
						hayMejora = true;
					}

	
				}			
				
	

	}
 }
	
		circ1.clear();
		circ2.clear();
		circ1 = (ArrayList<Integer>) circ1Res.clone();
		circ2 = (ArrayList<Integer>) circ2Res.clone();
	}
	circuito1 = (ArrayList<Integer>)circ1.clone();
	circuito2 = (ArrayList<Integer>)circ2.clone();
	
	setPesoCircuito1(pesoCircuito(circuito1));
	setPesoCircuito2(pesoCircuito(circuito2));
	
}
}
